package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure.util;

import javafx.scene.transform.Rotate;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class BTree {

    public static void main(String[] args) {
        BTreeNode node = new BTreeNode(7);
        node.setLeft(new BTreeNode(8));
        node.setRight(new BTreeNode(9));
        BTreeNode node1 = new BTreeNode(6);
        node1.setRight(node);
        node = new BTreeNode(5);
        node.setLeft(node1);
        node1 = new BTreeNode(4);
        node1.setRight(node);
        node = new BTreeNode(2);
        node.setLeft(node1);
        node1 = new BTreeNode(1);
        node1.setLeft(node);
        node1.setRight(new BTreeNode(3));
        BTreeNode root = node1;
        System.out.println("=========递归先序遍历=========");
        firstOrderTraverseRecursive(root);
        System.out.println();
        System.out.println("=========递归中序遍历=========");
        inOrderTraverseRecursive(root);
        System.out.println();
        System.out.println("=========递归后序遍历=========");
        lastOrderTraverseRecursive(root);
        System.out.println();
        System.out.println("=========非递归先序遍历=========");
        firstOrderTraverse(root);
        System.out.println();
        System.out.println("=========非递归中序遍历=========");
        inOrderTraverse(root);
        System.out.println();
        System.out.println("=========非递归后序遍历=========");
        lastOrderTraversewith2Stack(root);
        System.out.println();
        System.out.println("=========宽度优先遍历=========");
        widthFirstTraverse(root);
    }

    public static void firstOrderTraverse(BTreeNode root) {
        Stack<BTreeNode> stack = new Stack<>();
        BTreeNode node = root;
        if (node != null) {
            System.out.print(node.getValue() + " ");
            stack.push(node);
            node = node.getLeft();
        }
        while (node != null || !stack.empty()) {
            if (node != null) {
                System.out.print(node.getValue() + " ");
                stack.push(node);
                node = node.getLeft();
            } else {
                node = stack.pop();
                node = node.getRight();
            }
        }
    }

    public static void inOrderTraverse(BTreeNode root) {
        Stack<BTreeNode> stack = new Stack<>();
        BTreeNode node = root;
        if (node != null) {
            stack.push(node);
            node = node.getLeft();
        }
        while (node != null || !stack.empty()) {
            if (node != null) {
                stack.push(node);
                node = node.getLeft();
            } else {
                node = stack.pop();
                System.out.print(node.getValue() + " ");
                node = node.getRight();
            }
        }
    }

    public static void lastOrderTraverse(BTreeNode root) {
        Stack<BTreeNode> stack = new Stack<>();
        BTreeNode node = null;
        BTreeNode pre = null;

        if (root != null) {
            stack.push(root);
            while (!stack.empty()) {
                node = stack.peek();
                if ((node.getRight() == null && node.getLeft() == null) ||
                        (node.getRight() == pre && pre != null) ||
                        (node.getRight() == null && node.getLeft() == pre)) {
                    node = stack.pop();
                    System.out.print(node.getValue() + " ");
                    pre = node;
                } else {
                    if (node.getRight() != null) {
                        stack.push(node.getRight());
                    }
                    if (node.getLeft() != null) {
                        stack.push(node.getLeft());
                    }
                }
            }
        } else {
            return;
        }
    }

    public static void lastOrderTraversewith2Stack(BTreeNode root) {
        Stack<BTreeNode> stack = new Stack<>();
        Stack<Integer> integerStack = new Stack<>();

        BTreeNode node = root;
        if (node != null) {
            stack.push(node);
            integerStack.push(2);
            node = node.getLeft();
        }
        while (!stack.empty()) {
            if (node != null) {
                if (node != stack.peek()) {
                    stack.push(node);
                    integerStack.push(2);
                    node = node.getLeft();
                } else {
                    if (integerStack.peek() <= 0) {
                        node = stack.pop();
                        System.out.print(node.getValue() + " ");
                        integerStack.pop();
                        if (!stack.empty()) {
                            node = stack.peek();
                            int peek = integerStack.pop();
                            integerStack.push(--peek);
                        }
                    } else {
                        node = node.getRight();
                    }
                }
            } else {
                int peek = integerStack.pop();
                integerStack.push(--peek);
                node = stack.peek();
            }
        }
    }

    public static void widthFirstTraverse(BTreeNode root) {
        Queue<BTreeNode> queue = new ArrayDeque<>();
        BTreeNode node = root;
        if (node != null) {
            visit(node);
            queue.add(node);
        }
        while (!queue.isEmpty()) {
            node = queue.remove();
            if (node.getLeft() != null) {
                visit(node.getLeft());
                queue.add(node.getLeft());
            }
            if (node.getRight() != null) {
                visit(node.getRight());
                queue.add(node.getRight());
            }
        }
    }

    public static void firstOrderTraverseRecursive(BTreeNode root) {
        if (root != null) {
            System.out.print(root.getValue() + " ");
            firstOrderTraverseRecursive(root.getLeft());
            firstOrderTraverseRecursive(root.getRight());
        }
    }

    public static void inOrderTraverseRecursive(BTreeNode root) {
        if (root != null) {
            inOrderTraverseRecursive(root.getLeft());
            System.out.print(root.getValue() + " ");
            inOrderTraverseRecursive(root.getRight());
        }
    }

    public static void lastOrderTraverseRecursive(BTreeNode root) {
        if (root != null) {
            lastOrderTraverseRecursive(root.getLeft());
            lastOrderTraverseRecursive(root.getRight());
            System.out.print(root.getValue() + " ");
        }
    }

    private static void visit(BTreeNode node) {
        System.out.print(node.getValue() + " ");
    }
}
